﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 최소 전역 트리 문제
    /// O(E * LogV)
    /// </summary>
    class Prim
    {
        int[,] cost;
        int[] mincost;
        bool[] used;
        int vCount;

        public Prim(int[,] cost, int vCount)
        {
            this.cost = cost;
            this.vCount = vCount;
            mincost = new int[vCount + 1];
            used = new bool[vCount + 1];
            for (int i = 1; i <= vCount; i++)
            {
                mincost[i] = int.MaxValue;
                used[i] = false;
            }
        }
        public int MinCost()
        {
            mincost[1] = 0;
            int res = 0;
            while (true)
            {
                int v = -1;
                for (int u = 1; u <= vCount; u++)
                {
                    if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
                }
                if (v == -1) break;
                used[v] = true;
                Console.Write(v + "(" + mincost[v] +") ");
                res += mincost[v];

                for (int u = 1; u <= vCount; u++)
                {
                    if (cost[v, u] <= mincost[u])
                    {
                        mincost[u] = cost[v, u];
                    }
                }
            }
            return res;
        }
    }
}
